class Solution:
    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:
        left = []
        right = []
        for pos, amount in fruits:
            d = pos - startPos
            if d < -k:
                continue
            elif d < 0:
                left.append((-d, amount))
            elif d > k:
                break
            else:
                right.append((d, amount))
        # print(left)
        # print(right)
        m, n = len(left), len(right)

        # 先向右走，再折返向左
        ans = 0
        total = sum(x[1] for x in right)
        i = m-1
        for j in range(n-1, -1, -1):
            r = right[j][0]  # 当前向右走的距离
            l = k - 2*r  # 回头向左走的距离
            while i >= 0 and l >= left[i][0]:  # 加上从左边拿到的水果数量
                total += left[i][1]
                i -= 1
            # print(f"从右往左, {total=}, 最右到达的位置:{r+startPos}, 折返到达的位置{startPos-l}")
            if total > ans:
                ans = total

            if i < 0:  # 无法从左边拿到更多了
                break
            
            total -= right[j][1]  # 放弃拿最右边这个

        # 先向左走，再折返向右
        total = sum(x[1] for x in left)
        j = 0
        for l, amount in left:
            r = k - 2*l  # 回头向右走的距离
            while j < n and r >= right[j][0]:
                total += right[j][1]
                j += 1
            # print(f"从左往右, {total=}, 最左到达的位置:{startPos-l}, 折返到达的位置{startPos+r}")
            if total > ans:
                ans = total
            
            if j == n:  # 无法从右边拿到更多了
                break

            total -= amount  # 去掉最左边这个
        return ans